<html>
<head><meta charset="utf-8"><title>Longer term · t-compiler/wg-polonius · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/index.html">t-compiler/wg-polonius</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html">Longer term</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="247868782"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247868782" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247868782">(Aug 01 2021 at 17:31)</a>:</h4>
<p>In the long term, I want to make <code>datafrog</code> generic over multiple relation data structures, instead of requiring everything to be a sorted list of tuples. Move/init data tends to be pretty dense, so something as simple as a linear array of <code>BitSet</code>s might actually save memory, and  <strong>O</strong>(1) lookup will speed things up when the relation is large.  There are also some more advanced data structures that have fast range queries on dense data... <span aria-label="wink" class="emoji emoji-1f609" role="img" title="wink">:wink:</span></p>



<a name="247868905"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247868905" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247868905">(Aug 01 2021 at 17:34)</a>:</h4>
<p>In the short term, we could bypass move/init entirely by emitting (drop) liveness facts directly from <code>rustc</code>. These are dense as well, but</p>
<p>- a) it's only a single dense relation, as opposed to several<br>
  - b) we could do all the field-sensitive computations in <code>rustc</code> as opposed to Polonius</p>
<p>I don't really like this, since it seems like a nontrivial amount of work to put off something that we have to do anyway</p>



<a name="247869067"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869067" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869067">(Aug 01 2021 at 17:39)</a>:</h4>
<p><span class="user-mention silent" data-user-id="118594">Dylan MacKenzie (ecstatic-morse)</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Challenges.20for.20move.2Finit.2C.20liveness.2C.20and.20.60Location.3A.3AAll.60/near/247868782">said</a>:</p>
<blockquote>
<p>In the long term, I want to make <code>datafrog</code> generic over multiple relation data structures, instead of requiring everything to be a sorted list of tuples. Move/init data tends to be pretty dense, so something as simple as a linear array of <code>BitSet</code>s might actually save memory, and  <strong>O</strong>(1) lookup will speed things up when the relation is large.  There are also some more advanced data structures that have fast range queries on dense data... <span aria-label="wink" class="emoji emoji-1f609" role="img" title="wink">:wink:</span></p>
</blockquote>
<p>This also seems like something a suitably committed newbie could do, since you don't need a lot of familiarity with the borrow checker rules themselves.</p>



<a name="247869325"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869325" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869325">(Aug 01 2021 at 17:47)</a>:</h4>
<p>There's also <a href="https://github.com/rust-lang/polonius/issues/80">rust-lang/polonius#80</a>, which seems like it's an easy win, although it doesn't scale easily to multiple analyses, since points that are unintersting in one analysis (borrows and loans) may be interesting to another (initializedness) so you'd have to move from one compressed CFG to another as you move through the various analyses</p>



<a name="247869382"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869382" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869382">(Aug 01 2021 at 17:48)</a>:</h4>
<p><span class="user-mention" data-user-id="116113">@lqd</span> Is there anything you want done in the short-term? I'd like to write up some mentoring instructions for my idea, since it shouldn't make Polonius any more complex while we're still in the prototyping phase. It's all <code>datafrog</code></p>



<a name="247869455"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869455" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869455">(Aug 01 2021 at 17:50)</a>:</h4>
<p>sounds good to me actually. I don't know if you've also seen the couple PRs opened on datafrog recently ?</p>



<a name="247869465"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869465" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869465">(Aug 01 2021 at 17:50)</a>:</h4>
<p>FWIW, compressing the input facts on-disk seems like an easy win to me, and supporting multiple input methods is something we'll definitely want to do in the future (when all this data gets transferred in-memory), but it might not make a big difference? You have better intuition than I</p>



<a name="247869469"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869469" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869469">(Aug 01 2021 at 17:51)</a>:</h4>
<p>these PRs could be interesting to look at as well</p>



<a name="247869472"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869472" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869472">(Aug 01 2021 at 17:51)</a>:</h4>
<p><span class="user-mention silent" data-user-id="116113">lqd</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Challenges.20for.20move.2Finit.2C.20liveness.2C.20and.20.60Location.3A.3AAll.60/near/247869455">said</a>:</p>
<blockquote>
<p>sounds good to me actually. I don't know if you've also seen the couple PRs opened on datafrog recently ?</p>
</blockquote>
<p>No! Cool, I'll check them out now.</p>



<a name="247869478"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869478" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869478">(Aug 01 2021 at 17:51)</a>:</h4>
<p>(I just saw that my micro-optimizations got merged at some point during my open-source hiatus)</p>



<a name="247869552"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869552" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869552">(Aug 01 2021 at 17:53)</a>:</h4>
<p>what kinds of wins do you expect from compressing on disk (apart from the one where we don't have +1M diffs every time we update them of course ;) -- we should really mark them as binary in the repo) ? it should only matter for the polonius binary, ie when we manually run the benchmarks or tests, rather than for rustc</p>



<a name="247869569"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869569" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869569">(Aug 01 2021 at 17:53)</a>:</h4>
<p>hopefully eg prusti and others only use polonius-engine via the in-memory facts</p>



<a name="247869639"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869639" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869639">(Aug 01 2021 at 17:56)</a>:</h4>
<p>if datafrog is fun for you, there must be a lot of fun things to do there for sure :) some bitmap filters could be interesting for antijoins (maybe Lemire's recent Xor Filters / Binary Fuse Filters -- that sounds like fun :)</p>



<a name="247869683"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869683" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869683">(Aug 01 2021 at 17:56)</a>:</h4>
<p>(Revealing the depths of my naivete) Does one dump facts to disk when running the <code>rustc</code> test suite? Are there a lot of multiple GB fact files? If so, would expect multiple seconds to be spent just doing disk I/O</p>



<a name="247869696"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869696" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869696">(Aug 01 2021 at 17:57)</a>:</h4>
<p>and for real I'm sure I remember a paper from Paul Khuong where they benchmarked binary search in depth and either the eytzinger or vEB layout came out on top</p>



<a name="247869702"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869702" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869702">(Aug 01 2021 at 17:57)</a>:</h4>
<p>no no rustc uses the in-memory facts as well</p>



<a name="247869703"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869703" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869703">(Aug 01 2021 at 17:57)</a>:</h4>
<p>Yeah, I think you linked me to eytzinger layout one</p>



<a name="247869706"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869706" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869706">(Aug 01 2021 at 17:57)</a>:</h4>
<p>Ah well there you go <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span></p>



<a name="247869714"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869714" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869714">(Aug 01 2021 at 17:58)</a>:</h4>
<p>mostly only our in-tree benchmarks, and therefore some tests, should be the only users of the on-disk facts</p>



<a name="247869761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869761">(Aug 01 2021 at 17:58)</a>:</h4>
<p>So the 41GB you mention above is pure memory usage? Or do you dump facts to disk to get an idea of their size?</p>



<a name="247869762"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869762" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869762">(Aug 01 2021 at 17:58)</a>:</h4>
<p>but you're right that loading the bigger benchmarks, + interning, is slow AF</p>



<a name="247869773"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869773" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869773">(Aug 01 2021 at 17:59)</a>:</h4>
<p>it was pure on-disk dumps when I manually asked rustc to emit the facts files</p>



<a name="247869833"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869833" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869833">(Aug 01 2021 at 18:00)</a>:</h4>
<p>it's easier to obtain a rough estimate of the size and time it took to emit the on-disk facts + the actual tuples counts</p>



<a name="247869859"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869859" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869859">(Aug 01 2021 at 18:00)</a>:</h4>
<p>Yep, makes perfect sense to me</p>



<a name="247869879"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869879" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869879">(Aug 01 2021 at 18:00)</a>:</h4>
<p>(we can have the fact generation timing via rustc self-profiling)</p>



<a name="247869957"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869957" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869957">(Aug 01 2021 at 18:02)</a>:</h4>
<p>do you think we're at a point where we can actually work on HRTB or would we need more actionable items (we can produce such a list of actionable items next sprint) ?</p>



<a name="247869978"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869978" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869978">(Aug 01 2021 at 18:03)</a>:</h4>
<p><a href="https://github.com/rust-lang/datafrog/issues/34">rust-lang/datafrog#34</a> seems pretty cool BTW, although I haven't looked at the implementation</p>



<a name="247869986"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869986" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869986">(Aug 01 2021 at 18:03)</a>:</h4>
<p>we can probably add universes to the facts and so on, but if that's the only actionable item we can accomplish now there's no rush to do so</p>



<a name="247869988"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247869988" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247869988">(Aug 01 2021 at 18:03)</a>:</h4>
<p><span class="user-mention silent" data-user-id="116113">lqd</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Challenges.20for.20move.2Finit.2C.20liveness.2C.20and.20.60Location.3A.3AAll.60/near/247869957">said</a>:</p>
<blockquote>
<p>do you think we're at a point where we can actually work on HRTB ou would we need more actionable items (we can produce such a list of actionable items next sprint) ?</p>
</blockquote>
<p>I'm not, others might be, that higher-ranked errors conversation was like drinking from a fire hose</p>



<a name="247870034"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870034" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870034">(Aug 01 2021 at 18:04)</a>:</h4>
<p>nice, that's the one PR whose title seemed the most interesting :)</p>



<a name="247870037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870037">(Aug 01 2021 at 18:04)</a>:</h4>
<p>same, honestly :)</p>



<a name="247870137"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870137" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870137">(Aug 01 2021 at 18:07)</a>:</h4>
<p>The canonical example for HRTBs and the borrow checker is like:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">fn</span> <span class="nf">foo</span><span class="o">&lt;'</span><span class="na">a</span><span class="o">&gt;</span><span class="p">(</span><span class="n">a</span>: <span class="kp">&amp;</span><span class="o">'</span><span class="na">a</span> <span class="kt">u32</span><span class="p">)</span><span class="w"> </span><span class="k">where</span><span class="w"> </span><span class="k">for</span><span class="o">&lt;'</span><span class="na">b</span><span class="o">&gt;</span><span class="w"> </span><span class="o">'</span><span class="na">a</span><span class="w"> </span>: <span class="o">'</span><span class="na">b</span> <span class="p">{</span><span class="w"> </span><span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">bar</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">22</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">y</span>: <span class="kp">&amp;</span><span class="o">'</span><span class="na">y</span> <span class="kt">u32</span> <span class="o">=</span><span class="w"> </span><span class="o">&amp;</span><span class="n">x</span><span class="p">;</span><span class="w"> </span><span class="c1">// giving a name 'y here for convenience</span>
<span class="w">    </span><span class="n">foo</span>::<span class="o">&lt;'</span><span class="na">y</span><span class="o">&gt;</span><span class="p">(</span><span class="n">y</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>But we don't <em>need</em> universes to handle this, since <code>for&lt;'b&gt;  'a: 'b</code> can be reduced to <code>'a: 'static</code></p>



<a name="247870187"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870187" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870187">(Aug 01 2021 at 18:08)</a>:</h4>
<p>(for datafrog, there are some recent cool sorting papers, or some of Lemire's work on SIMD galloping and set intersections that would probably be fun and useful)</p>



<a name="247870213"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870213" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870213">(Aug 01 2021 at 18:08)</a>:</h4>
<p>I think I'm failing to understand the boundary between type-checking/trait-solving and borrow-checking</p>



<a name="247870220"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870220" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870220">(Aug 01 2021 at 18:08)</a>:</h4>
<p>+1 :)</p>



<a name="247870225"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870225" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870225">(Aug 01 2021 at 18:08)</a>:</h4>
<p>And some more complex examples would be helpful</p>



<a name="247870230"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870230" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870230">(Aug 01 2021 at 18:09)</a>:</h4>
<p>Boy I've really polluted this thread</p>



<a name="247870244"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870244" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870244">(Aug 01 2021 at 18:09)</a>:</h4>
<p>probably the canonical example would have to be involving subset relationships where one origin is in a universe that can't name the other</p>



<a name="247870246"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870246" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870246">(Aug 01 2021 at 18:09)</a>:</h4>
<p><span class="user-mention silent" data-user-id="116113">lqd</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Challenges.20for.20move.2Finit.2C.20liveness.2C.20and.20.60Location.3A.3AAll.60/near/247870187">said</a>:</p>
<blockquote>
<p>(for datafrog, there are some recent cool sorting papers, or some of Lemire's work on SIMD galloping and set intersections that would probably be fun and useful)</p>
</blockquote>
<p>Yeah, and all of this stuff is non-intrusive and beginner-friendly (like beginner to Rust, you still have to know what you're doing)</p>



<a name="247870292"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870292" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870292">(Aug 01 2021 at 18:10)</a>:</h4>
<p><span class="user-mention silent" data-user-id="118594">Dylan MacKenzie (ecstatic-morse)</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Longer.20term/near/247870230">said</a>:</p>
<blockquote>
<p>Boy I've really polluted this thread</p>
</blockquote>
<p>fixed :)</p>



<a name="247870306"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870306" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870306">(Aug 01 2021 at 18:10)</a>:</h4>
<p><span class="user-mention silent" data-user-id="116113">lqd</span> <a href="#narrow/stream/186049-t-compiler.2Fwg-polonius/topic/Challenges.20for.20move.2Finit.2C.20liveness.2C.20and.20.60Location.3A.3AAll.60/near/247870244">said</a>:</p>
<blockquote>
<p>probably the canonical example would have to be involving subset relationships where one origin is in a universe that can't name the other</p>
</blockquote>
<p>Okay, so this example appears in the dev-guide</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">fn</span> <span class="nf">bar</span><span class="o">&lt;'</span><span class="na">a</span><span class="p">,</span><span class="w"> </span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="n">t</span>: <span class="kp">&amp;</span><span class="o">'</span><span class="na">a</span> <span class="nc">T</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">x</span>: <span class="nc">for</span><span class="o">&lt;'</span><span class="na">b</span><span class="o">&gt;</span><span class="w"> </span><span class="k">fn</span><span class="p">(</span><span class="o">&amp;'</span><span class="na">b</span><span class="w"> </span><span class="kt">u32</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o">..</span><span class="p">.;</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">y</span>: <span class="nc">for</span><span class="o">&lt;'</span><span class="na">c</span><span class="o">&gt;</span><span class="w"> </span><span class="k">fn</span><span class="p">(</span><span class="o">&amp;'</span><span class="na">b</span><span class="w"> </span><span class="kt">u32</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o">..</span><span class="p">.;</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="247870312"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870312" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870312">(Aug 01 2021 at 18:11)</a>:</h4>
<p>(I'll go grab dinner now, good talking to you, as always :)</p>



<a name="247870313"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870313" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870313">(Aug 01 2021 at 18:11)</a>:</h4>
<p>Is this what you're thinking about?</p>



<a name="247870314"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870314" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870314">(Aug 01 2021 at 18:11)</a>:</h4>
<p>yes</p>



<a name="247870315"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870315" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870315">(Aug 01 2021 at 18:11)</a>:</h4>
<p>You too <span class="user-mention" data-user-id="116113">@lqd</span></p>



<a name="247870321"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870321" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870321">(Aug 01 2021 at 18:11)</a>:</h4>
<p>these examples from the dev guide where eg <code>'b: 'a</code> where <code>'b</code> is a placeholder in a universe <code>'a</code> can't name (IIRC)</p>



<a name="247870380"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870380" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870380">(Aug 01 2021 at 18:13)</a>:</h4>
<p>Okay, I'll spend some time thinking about that type of program (filling in the ellipses), even generating some more test cases would be worthwhile I think, even if I can't solve them before getting more help from Niko</p>



<a name="247870385"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247870385" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247870385">(Aug 01 2021 at 18:13)</a>:</h4>
<p>Enjoy your meal!</p>



<a name="247875586"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247875586" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247875586">(Aug 01 2021 at 20:24)</a>:</h4>
<p>there definitely are rustc UI tests with HRTBs that don't trigger polonius errors. I'm not sure how the universes show up there in the subtyping relatonships but I'll find the ones I'm thinking of</p>



<a name="247875865"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247875865" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247875865">(Aug 01 2021 at 20:33)</a>:</h4>
<p>this one is basically the same as the canonical example from above <a href="https://github.com/rust-lang/rust/blob/master/src/test/ui/issues/issue-26217.rs">https://github.com/rust-lang/rust/blob/master/src/test/ui/issues/issue-26217.rs</a></p>



<a name="247879851"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247879851" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247879851">(Aug 01 2021 at 22:17)</a>:</h4>
<p>Right, yeah. From the "quantifier elimination"  POV, you would  rewrite the bound on <code>foo</code> as <code>T: 'static</code> during constraint generation, much like the other example.</p>



<a name="247879984"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247879984" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247879984">(Aug 01 2021 at 22:20)</a>:</h4>
<p>Whereas from the universe POV, you have <code>'foo</code> (<code>'a</code> in <code>foo</code>) in U1, and <code>'bar</code> in U0, and also an implied bound like <code>'bar: 'foo</code>, which means you replace <code>'foo</code> with <code>'static</code>?</p>



<a name="247879988"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247879988" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247879988">(Aug 01 2021 at 22:21)</a>:</h4>
<p>(My intuition for the universe rules is very poor)</p>



<a name="247880745"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247880745" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247880745">(Aug 01 2021 at 22:42)</a>:</h4>
<p>I suspect there's a more complex case where not everything is immediately available, so quantifier eliminations "can't see" what substitution needs to be done but the universe check can still handle things, but I don't think I've seen one yet.</p>



<a name="247880750"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/186049-t-compiler/wg-polonius/topic/Longer%20term/near/247880750" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/186049-t-compiler/wg-polonius/topic/Longer.20term.html#247880750">(Aug 01 2021 at 22:42)</a>:</h4>
<p>And I'm not as good as Niko at materializing examples.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>